package interview;

/**
 * 线上某天某个人发布一个有问题的代码版本上线，在此版本后续所有的代码都是有问题的。
 * <p>
 * 现在已经有一个工具类函数 checkRight 可以检测出有问题的代码版本，给定发布以来所有的代码版本号（**已经按照提交时间排序**），写一段程序找到第一个有问题的代码版本。
 * <p>
 * 要求：
 * <p>
 * - 实现 findFirstWrong 函数
 * - checkRight 可以直接调用，不需要考虑它的实现方式。这里仅仅给了一个Demo的实现。
 * - checkRight 本身是*耗时的，需要减少对它的调用*
 * - 需要考虑*算法时间复杂度*
 * - 先说说**思路**，以及算法的时间复杂度
 * - **关掉所有的AI编程助手，比如 Copilot 等**
 * - 20min 以内
 * <p>
 * P.S 代码版本号是如下图红框圈出来的 git commit hash值。
 */
public class FindFirstWrongAns {

    public static void main(String[] args) {

        // String[] versions = new String[]{"1", "2", "3", "wrong1", "wrong2"};
        String[] versions = new String[]{"wrong1", "wrong2"};
        // String[] versions = new String[]{"1", "2", "3", "4", "wrong1", "wrong2"};
//        String[] versions = new String[]{"hash1", "abcd2", "qoweioqhw3","doadjadj4", "wrong1ashdauhdu", "wrong2qweqweqwe"};
//        String[] versions = new String[]{"hash1", "abcd2", "qoweioqhw3","doadjadj4", "wrong1ashdauhdu"};
        System.out.println(findFirstWrong(versions));
    }


    /**
     * Retrieve the first version of the code that contains bugs and is incorrect.
     *
     * @param versions An array of code versions ordered by commit time.
     * @return The first incorrect version of the code.
     */
    public static String findFirstWrong(String[] versions) {
        int l = 0, r = versions.length, n = versions.length;
        while (l < r) {
            int m = (l + r) >> 1;
            boolean isRight = checkRight(versions[m]);
            if (isRight) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l == n ? versions[n - 1] : versions[l];
    }

    /**
     * Verify the correctness and absence of bugs in the code.
     *
     * @param version The hash of the code from a commit.
     * @return True if the code version is correct; otherwise, return False.
     */
    public static boolean checkRight(String version) {

        // Just mock some time consuming check
        doSomeTimeConsumingCheck();

        if (version.startsWith("wrong")) {
            return false;
        } else {
            return true;
        }
    }

    public static void doSomeTimeConsumingCheck() {
        try {
            Thread.sleep(1000L);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }

}